home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 11 Learning / 04 Mommersteeg / Predictors / ImprovedPredictor.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-09-24  |  4.9 KB  |  146 lines
  1. //----------------------------------------------------------------------------------------------
  2. // Sequential Prediction Demo: The positioning pattern
  3. // 
  4. // Author:  Fri Mommersteeg
  5. // Date:    10-09-2001
  6. // File:    ImprovedPredictor.cpp
  7. //----------------------------------------------------------------------------------------------
  8.  
  9. //----------------------------------------------------------------------------------------------
  10. // Include files
  11. //----------------------------------------------------------------------------------------------
  12.  
  13. #include "StdAfx.h"
  14. #include "ImprovedPredictor.h"
  15.  
  16. //----------------------------------------------------------------------------------------------
  17. // Update(): updates the predictor with the next element in the sequence
  18. //----------------------------------------------------------------------------------------------
  19.  
  20. void CImprovedPredictor::Update(int NextElement) {
  21.  
  22.     // calculate lenghts of all substrings matching the tail
  23.     int nSize = m_Histogram[NextElement].GetSize();
  24.  
  25.     // clear alphabet array
  26.     for (int n = 0; n < m_Alphabet.GetSize(); n++) {
  27.         m_Alphabet[n] = 0.0f;
  28.     }
  29.     
  30.     // clear total prediction value;
  31.     m_TotalPredictionValue = 0.0f;
  32.  
  33.     int i = 0;
  34.     // find all occurrences of NextElement in the window
  35.     while (i < nSize) {
  36.  
  37.         // retrieve the i-th occurence of NextElement
  38.         THistogramData & hd = m_Histogram[NextElement][i];
  39.         
  40.         // determine the distance of this substring to the tail
  41.         int DistanceToTail = (m_nSequenceLength - hd.nSequencePosition);
  42.         
  43.         // determine the position of this occurrence in the window
  44.         int iWindowPosition = m_Window.GetSize() - DistanceToTail;
  45.  
  46.         if (HasNeighbour(iWindowPosition, m_PrevElement)) {
  47.             // if this occurrence is preceded by PrevElement, we create a longer substring
  48.             m_Window[iWindowPosition].nMatchSize = GetNeighbourSize(iWindowPosition) + 1;
  49.         } else {
  50.             // else the size of this substring has to be one
  51.             m_Window[iWindowPosition].nMatchSize = 1;
  52.         }
  53.  
  54.         // calculate the prediction value of this substring
  55.         float PredictionValue = (float)(m_Window[iWindowPosition].nMatchSize) / (float)DistanceToTail;
  56.     
  57.         int Successor;
  58.  
  59.         // get the successor element of this matching substring
  60.         if (iWindowPosition == m_Window.GetSize()-1) {
  61.             Successor = NextElement;
  62.         } else {
  63.             Successor = m_Window[iWindowPosition + 1].Element;
  64.         }
  65.  
  66.         // add this prediction value to this element
  67.         m_Alphabet[Successor] += PredictionValue;
  68.  
  69.         // update total prediction value (used to normalize the predictions later on)
  70.         m_TotalPredictionValue += PredictionValue;
  71.  
  72.         i++;
  73.     }
  74.  
  75.     // add NextElement to the histogram 
  76.     m_Histogram[NextElement].AddHead(THistogramData(m_nSequenceLength));
  77.  
  78.     // remove element dropped from the window also from histogram
  79.     TSequenceData * pDropped = m_Window.Add(TSequenceData(NextElement));
  80.     if (pDropped != NULL) {        
  81.         m_Histogram[pDropped->Element].RemoveTail();
  82.     }
  83.  
  84.     // update predictor/sequence information
  85.     m_nSequenceLength++;
  86.     m_PrevElement = NextElement;
  87.  
  88.     // calculate predicted successor
  89.     CalculatePrediction();
  90. }
  91.  
  92. //----------------------------------------------------------------------------------------------
  93. // CalculatePrediction(): calculates the best possible prediction
  94. //----------------------------------------------------------------------------------------------
  95.  
  96. void CImprovedPredictor::CalculatePrediction() {
  97.     int i;
  98.  
  99.     if (m_TotalPredictionValue > 0) {
  100.  
  101.         // normalize prediction values
  102.         for (i = 0; i < m_Alphabet.GetSize(); i++) {
  103.             m_Alphabet[i] /= m_TotalPredictionValue;
  104.         }
  105.  
  106.         // find element with the highest prediction value
  107.         m_HighestPredictionValue = 0.0f;    
  108.         for (i = 0; i < m_Alphabet.GetSize(); i++) {
  109.             if (m_Alphabet[i] > m_HighestPredictionValue) {
  110.                 m_HighestPredictionValue = m_Alphabet[i];
  111.                 m_nPrediction = i;
  112.             }
  113.         }
  114.  
  115.     } else {
  116.         m_nPrediction = 0;
  117.     }
  118. }
  119.  
  120. //----------------------------------------------------------------------------------------------
  121. // GetPrediction(): returns the best possible prediction
  122. //----------------------------------------------------------------------------------------------
  123.  
  124. bool CImprovedPredictor::GetPrediction(int &Prediction) {
  125.     // return cached prediction value
  126.     Prediction = m_nPrediction;
  127.     return m_HighestPredictionValue >= m_fMinPerformance;
  128. }
  129.  
  130. //----------------------------------------------------------------------------------------------
  131. // Setup(): sets up the predictor
  132. //----------------------------------------------------------------------------------------------
  133.  
  134. void CImprovedPredictor::Setup(int nWindowSize, int nAlphabetSize, float fMinPerformance) {
  135.     // set up window
  136.     m_nWindowSize = nWindowSize;
  137.     m_Window.SetSize(nWindowSize);
  138.  
  139.     // set up histogram
  140.     m_nAlphabetSize = nAlphabetSize;
  141.     m_Histogram.SetSize(nAlphabetSize);
  142.     m_Alphabet.SetSize(nAlphabetSize);
  143.  
  144.     m_fMinPerformance = fMinPerformance;    
  145. }
  146.